class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
}

//      链表内指定区间反转


//  解法一：双指针(两次遍历)
public class demo {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // 取出需要翻转的部分left right
        ListNode dummy = new ListNode(-1);//不能为null
        dummy.next = head;
        ListNode pre = dummy;// 需要翻转的头节点的前驱
        // 找到m的前一个节点
        for (int i=0; i<m-1; i++) {
            pre = pre.next;
        }
        // m节点
        ListNode left = pre.next;
        // 找到n节点
        ListNode right = pre;
        for (int i=0; i<n-m+1; i++) {
            right = right.next;
        }

        // n的后一个节点
        ListNode cur = right.next;

        // 切断联系
        pre.next = null;
        right.next = null;

        // 翻转部分链表
        reverseLinkList(left);

        // 建立联系
        pre.next = right;
        left.next = cur;

        return dummy.next;
    }



    // 翻转链表
    public void reverseLinkList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode Cur_next = null;
        while (cur != null) {
            Cur_next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = Cur_next;
        }
    }











//    解法二：一次遍历（对解法一的优化）
    public ListNode reverseBetween2 (ListNode head, int m, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i=0; i<m-1; i++) {
            pre = pre.next;
        }

        ListNode cur = pre.next;
        // ListNode Cur_next = cur.next;// error 这个要在循环里面
        ListNode Cur_next = null;


        for (int i=0; i<n-m; i++) {
            Cur_next = cur.next;

            // 中右左(指向顺序)
            cur.next = Cur_next.next;
            Cur_next.next = pre.next;
            pre.next = Cur_next;
        }

        return dummy.next;
    }
}
